package com.feng.leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class L40 {
    public static void main(String[] args) {
//        int[] candidates = {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1};
//        int[] candidates ={14,6,25,9,30,20,33,34,28,30,16,12,31,9,9,12,34,16,25,32,8,7,30,12,33,20,21,29,24,17,27,34,11,17,30,6,32,21,27,17,16,8,24,12,12,28,11,33,10,32,22,13,34,18,12};
        int[] candidates ={14,18,19,30,6,5,14,23,28,18,26,21,12,15,29,18,32,23,6,21,19,30,6,28,17,13,29,28,10,34,26,11,10,32,7,11,32,8,21,18,22,5,34,21,7,20,26,5,9,28,21,23,23,15,8,27,23,32,12,20,31,33,27,28,30,21,34,19};
//        int[] candidates ={10,1,2,7,6,1,5};
        long l = System.currentTimeMillis();

//        int[] candidates = {5,1,5,4,3,3};
        int target = 29;
        List<List<Integer>> lists = combinationSum2(candidates, target);
        System.out.println(System.currentTimeMillis() - l);
        System.out.println(lists);
    }

    public static List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> all = new ArrayList<>();
        List<Integer> result = new LinkedList<>();
        List<Integer> recode = new ArrayList<>();
        Arrays.sort(candidates);
//        digui(all,result,0,candidates,target,0);
        digui(all,result,0,candidates,target,0,recode);
        return all;
    }
    private static void digui(List<List<Integer>> all, List<Integer> result, int i, int[] candidates, int target, int sum) {
        if (sum == target) {
            for (List<Integer> list : all) {
                if (list.size() == result.size() && list.containsAll(result) && result.containsAll(list)) {
                    return;
                }
            }

            all.add(new LinkedList<>(result));
            return;
        }
        if (sum > target || i == candidates.length) {
            return;
        }
        sum += candidates[i];
        result.add(candidates[i]);
        digui(all,result,i+1,candidates,target,sum);
        sum -= candidates[i];
        result.remove(result.size()-1);
        digui(all,result,i+1,candidates,target,sum);
    }
    private static void digui(List<List<Integer>> all, List<Integer> result, int i, int[] candidates, int target, int sum, List<Integer> recode) {
        if (sum == target) {
            for (List<Integer> list : all) {
                if (list.size() == result.size() && list.containsAll(result) && result.containsAll(list)) {
                    return;
                }
            }

            all.add(new LinkedList<>(result));
            return;
        }
        if (sum > target || i == candidates.length) {
            return;
        }

        if (sum == 0 && result.size()==0) {
            recode.add(candidates[i]);
        }
        sum += candidates[i];
        result.add(candidates[i]);
        digui(all,result,i+1,candidates,target,sum, recode);
        sum -= candidates[i];
        result.remove(result.size()-1);

        for (int j = i+1; j < candidates.length; j++) {
            if (candidates[j] > target - sum) {
                break;
            }
            if (candidates[j] == candidates[i] || (sum == 0 && result.size() == 0 && recode.contains(candidates[j]))) {
                continue;
            }else {
                digui(all,result,j,candidates,target,sum, recode);
                break;
            }
        }
    }
}
